{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。\n",
    "\n",
    "## 示例 1：\n",
    "```\n",
    "输入：nums1 = [1,3], nums2 = [2]\n",
    "输出：2.00000\n",
    "解释：合并数组 = [1,2,3] ，中位数 2\n",
    "```\n",
    "## 示例 2：\n",
    "```\n",
    "输入：nums1 = [1,2], nums2 = [3,4]\n",
    "输出：2.50000\n",
    "解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5\n",
    "```\n",
    "## 示例 3：\n",
    "```\n",
    "输入：nums1 = [0,0], nums2 = [0,0]\n",
    "输出：0.00000\n",
    "```\n",
    "## 示例 4：\n",
    "```\n",
    "输入：nums1 = [], nums2 = [1]\n",
    "输出：1.00000\n",
    "```\n",
    "## 示例 5：\n",
    "```\n",
    "输入：nums1 = [2], nums2 = []\n",
    "输出：2.00000\n",
    "``` \n",
    "\n",
    "\n",
    "## 提示：\n",
    "\n",
    "```\n",
    "nums1.length == m\n",
    "\n",
    "nums2.length == n\n",
    "\n",
    "0 <= m <= 1000\n",
    "\n",
    "0 <= n <= 1000\n",
    "\n",
    "1 <= m + n <= 2000\n",
    "\n",
    "-106 <= nums1[i], nums2[i] <= 106\n",
    "```\n",
    "\n",
    "\n",
    "## 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "# 第一种写法："
   ],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 记录二分查找的信息\n",
    "### 怎么二分查找呢？\n",
    "- 假设两个序列按顺序合并了，那么中间点的位置就在(len1 + len2 + 1) // 2\n",
    "- 假定这个理想中位数为x\n",
    "- 考虑一般情况下，第一个序列存在一个数，其左边都是小于x，右边都大于x。\n",
    "- 对第二个序列也是一样。\n",
    "- 我们对这两个数在各自序列的位置分别称作mid1和mid2。\n",
    "- 所以我们首先先对第一个序列二分查找。\n",
    "- 记录左边界，右边界为第一个序列的左右边界。\n",
    "- 而查找的中间就是左右边界的中间点。\n",
    "- 对于mid2，便是(len1 + len2 + 1) // 2减去mid1\n",
    "```\n",
    "left, right, half_len = 0, len1, (len1 + len2 + 1) // 2\n",
    "mid1 = (left + right) // 2\n",
    "mid2 = half_len - mid1\n",
    "```\n",
    "\n",
    "作者：qsctech-sange\n",
    "链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/dong-yong-er-fen-cha-zhao-mo-ban-lai-qiao-miao-jie/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "source": [
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        if len(nums1) > len(nums2):\n",
    "            nums1, nums2 = nums2, nums1 # swap减少二分查找次数,把nums1 设置为较短的数列\n",
    "            \n",
    "        m, n = len(nums1), len(nums2)\n",
    "        mark = (m+n-1) // 2 # 总长度切半,half_len\n",
    "        l, r = 0, m # nums1的左右边界\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2 # nums1 切半，取中间的位置值。\n",
    "            if mark-mid-1 < 0 or nums1[mid] >= nums2[mark-mid-1]:\n",
    "                # mark-mid-1；总长度切半 - nums1切半。\n",
    "                # nums1[mid] nums1 的中间位 >= nums2[mark-mid-1] nums2\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        middlepoints = sorted(nums1[l:l+2] + nums2[mark-l:mark-l+2])\n",
    "        return (middlepoints[0] + middlepoints[1-(m+n)%2]) / 2.0\n",
    "    "
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "# 第二种写法："
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "source": [
    "class Solution:\n",
    "    def findMedianSortedArrays(self, nums1, nums2):\n",
    "        if (l1 := len(nums1)) > (l2 := len(nums2)):\n",
    "            nums1, nums2 = nums2, nums1\n",
    "            m, n = l2, l1\n",
    "        else:\n",
    "            m, n = l1, l2\n",
    "\n",
    "        if m == 0:\n",
    "            if n & 1 == 0:\n",
    "                return (nums2[n // 2] + nums2[n // 2 - 1]) / 2\n",
    "            else:\n",
    "                return nums2[n // 2]\n",
    "\n",
    "        nums1 = [-1000001] + nums1 + [1000001]\n",
    "        nums2 = [-1000001] + nums2 + [1000001]\n",
    "\n",
    "        left = 1\n",
    "        right = m + 1\n",
    "        half_len = (m + n) // 2 + 2\n",
    "        while left <= right:\n",
    "            i = (left + right) // 2\n",
    "            j = half_len - i\n",
    "            if nums1[i - 1] <= nums2[j]:\n",
    "                left = i + 1\n",
    "            else:\n",
    "                right = i - 1\n",
    "        i = right\n",
    "        j = half_len - i\n",
    "        if (m + n) & 1 == 0:\n",
    "            return (max(nums1[i - 1], nums2[j - 1]) + min(nums1[i], nums2[j])) / 2\n",
    "        else:\n",
    "            return min(nums1[i], nums2[j])"
   ],
   "outputs": [],
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 执行检验："
   ],
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "source": [
    "if __name__ == '__main__':\n",
    "    l1 = [1,2,3,4,5,6]\n",
    "    l2 = [1,2,3,4,5,6,7,8,9]\n",
    "    a = Solution()\n",
    "    b = a.findMedianSortedArrays(l1, l2)\n",
    "    print(b)"
   ],
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "4.0\n"
     ]
    }
   ],
   "metadata": {}
  }
 ],
 "metadata": {
  "orig_nbformat": 4,
  "language_info": {
   "name": "python",
   "version": "3.9.0",
   "mimetype": "text/x-python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "pygments_lexer": "ipython3",
   "nbconvert_exporter": "python",
   "file_extension": ".py"
  },
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3.9.0 64-bit ('universe': virtualenv)"
  },
  "interpreter": {
   "hash": "efc9d12c894566d142e82a9dae601d559d62f10cdf97a3f3ead6efac69d368e5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}